package com.base.heap;

import com.base.dynamicprograming.KInversePairs;

import java.util.*;

/**
 * 786. 第 K 个最小的素数分数
 *
 * @author leon
 * @date 2021年11月29日 13:50
 */
public class KthSmallestPrimeFraction {

    /**
     * 暴力遍历+排序
     * @param arr
     * @param k
     * @return
     */
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {

        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                list.add(new int[]{arr[i],arr[j]});
            }
        }
        Collections.sort(list, (o1,o2) -> o1[0]*o2[1]-o2[0]*o1[1]);
        return list.get(k-1);

    }

    public int[] kthSmallestPrimeFraction1(int[] arr, int k){
        // 定义一个容量大小为k的大根堆
        // 入堆有两种情况：
        // 1、堆没有满，直接入
        // 2、堆满了，就和堆顶比较，如果大于堆顶，就不用入了，因为肯定不是第k小的元素，如果小了，就删除堆顶，入堆
        Comparator<int[]> comparator = (o1, o2) -> o2[0]*o1[1]-o1[0]*o2[1];
        PriorityQueue<int[]> heap = new PriorityQueue<>(k,comparator);
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                int[] tmp = new int[]{arr[i],arr[j]};
                if (heap.size()<k){
                    heap.add(tmp);
                }else {
                    if (comparator.compare(heap.peek(), tmp)<0){
                        heap.poll();
                        heap.add(tmp);
                    }

                }
            }
        }

        return heap.peek();

    }

    public static void main(String[] args) {
        new KthSmallestPrimeFraction().kthSmallestPrimeFraction(new int[]{1,5,17,29,41,43,61,73,83},21);
    }
}
